View AN3334_7692247.PDF datasheet online --- IC-ON-LINE

Datasheet File OCR Text:

freescale semiconductor application note document number: AN3334 rev. 0, 11/2006 contents ? freescale semiconductor, inc., 2006. all rights reserved. 1 introduction this application note presents data structures useful in developing microcontroller software. you can apply these basic data structures in a microcontroller application. a data structure describes how information is organized and stored in a comput er system. although data structures are usually pres ented in the context of computers, the same princi ples can be applied to embedded 8-bit processors. the efficient use of appropriate data structur es can improve both the dynamic (time-based) and static (storage-based) performance of microcontroller software. the rs08 core differs from other freescale 8-bit cores, in that it does not have a st ack pointer or index register (data structures use both). software can recover these feature, as shown in this application note. for other freescale 8-bit core examples, refer to freescale document-order number an1752. 1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1 storing strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 accessing strings . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 string applications. . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1 stack reading and writing . . . . . . . . . . . . . . . . . . . 4 3.2 mcu hardware stack . . . . . . . . . . . . . . . . . . . . . . . 4 3.3 rs08 stack applications . . . . . . . . . . . . . . . . . . . . . 5 4 queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.1 reading and writing . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2 queue errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.3 queue applications . . . . . . . . . . . . . . . . . . . . . . . . . 8 5 multiple access circul ar queue (macq) . . . . . . . . . . . 11 5.1 applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6 tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.1 table applications . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.2 table example. . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7 linked lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7.1 linked list applications . . . . . . . . . . . . . . . . . . . . . 18 7.2 state machines . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 7.3 state machine example. . . . . . . . . . . . . . . . . . . . . 19 7.4 simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 8 summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 data structures for rs08 microcontrollers by: inga harris 8-bit microcontroller applications engineer east kilbride, scotland free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 strings freescale semiconductor 2 the code in this application not e is written for the mc9rs08ka2 and tested using codewarrior ? 5.1 software and the demo9rs08ka2 board. 2 strings a string is a sequence of elements acc essed in sequential order. the string data structure usually refers to a sequence of characters. for example, a message output to a display is stored in memory as a string of ascii character bytes. 2.1 storing strings a start and end address iden tify a string of elements. a string?s star ting address can be defined in two ways: using an absolute address label or a base address with an offset. you can terminate string information in several ways . one common way is by using a special character to mark the end of the string. one term inating character is $04, which is an ascii eot (end- of-transmission) byte. figure 1 shows an example of string data. figure 1. string data structure another method of terminating a string is to identify its length. its length can then be used as a counter value, eliminating the need for an extra byte of storage for the end of the string. if you use the sign bit (the most significant bit) to indicate the last byte of the string, you can terminate a string of ascii characters without us ing an extra byte of storage. beca use ascii character data is only seven bits long, the last byte of a string can be indi cated by a 1 in its most significant bit location. when using this method, strip off the sign bit before using the ascii character value. h e l l o $04 address $50 $51 $52 $53 $54 $55 message pointer data free datasheet http:///
stacks data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 3 2.2 accessing strings an efficient way to access a string is with the indexed addressing mode and the inc or dec instructions. string storage and access: ;*********************************************************************** ;* string display code * ;* a generic method of displaying an entire string * ;*********************************************************************** org romstart _startup: mainloop: lda #message tax loop lda $0e ;load accumulator with the ;contents of the memory address ;pointed to by x cmp #$04 ;is it eot? ;user needs to write following routines ;beq stringdone ;jsr showbyte incx ;move to next byte bra loop ;*********************** *********************************************** ;* string storage example * ;* string is stored in ram * ;*********************************************************************** org ramstart message equ * message1 dc.b 'this is a string' dc.b $04 message2 dc.b "this is another string" dc.b $04 2.3 string applications practical applications of st rings include storing predefined canned messa ges. this is useful for applications requiring output to text displays, giving user s information, or prompting users for input. strings are also effective for stori ng initialization strings for hardware such as modems. strings may also store predefined command and data seque nces to communicate with other devices. 3stacks a stack is a series of da ta elements accessed only at one end. an an alogy for this data structure is a stack of dinner plates; the first pl ate placed on the stack is th e last plate taken from th e stack. for this reason, the stack is considered a last-in, first-ou t (lifo) structure. the stack is usef ul when the latest data is desired. a stack typically has a pr edefined maximum size. free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 stacks freescale semiconductor 4 figure 2 shows a representation of a stack. figure 2. stack data structure just like a physical stack of items, the software st ack has a bottom and a top. so ftware should keep track of the location of the top of the stac k. this address can point to the first piece of valid data or to the next available location. the code in section 3.3, ?rs08 stack applications ,? uses the latter option; it points to the next available location. 3.1 stack reading and writing a stack-read operation is called pulling, and a stack write operation is pushing. when you pull data from the stack, the data is removed and the stack pointer adjusts. when you push data onto the stack, data adds to the stack, and the stack pointer adjusts. in the implementation of figure 2 , a push operation first stor es the data to the address pointed to by the stack pointer and then decrement the stack pointer. a pull operation retrieves th e data the stack pointer points to and then increments the stack pointer. two error conditions are intrinsic to this data stru cture: underflow and overflow. a stack underflow occurs when you attempt to pull information off an empty st ack. a stack overflow occurs when you attempt to push information onto a full stack. wh en using this data structure, th ese conditions should be attended to. an underflow condition should return an error. on an ove rflow, you can reject the data and return an error, or the stack can wrap around to the bottom, de stroying the data at the bottom of the stack. 3.2 mcu hardware stack mcus use a stack structure for saving program cont ent before transferring program control. this interaction may be the result of a jump or interrupt. in the event of an interrupt, the stack pushes the values in the x (index register), a (accumulator), and ccr (con dition code register) regist ers, as well as the pc (program counter) value. when enc ountering a jump instruction, the pc value is pushed onto the stack. on returning from an interrupt (rti in struction), the program registers and pc are pulled from the stack. when returning from a jump (rts instruct ion), the pc is pulled from the stack. empty empty empty data byte data byte data byte data byte data byte stack pointer stack top (maximum) stack grows in this direction stack bottom $50 $51 $52 $53 $54 $55 $56 $57 data address free datasheet http:///
stacks data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 5 3.2.1 rs08 stack the rs08 family of mcus have no st ack-pointer registers in the core and, therefore, no automatic program control. section 7, ?linked lists ,? shows a macro managing the use of the shadow program counter (spc) for nested subroutines. the rest of this chapter de scribed a generic stack appl ication adaptable for any application need. 3.3 rs08 stack applications a stack is useful for dynamically allocating memory or pa ssing parameters to and from subroutines. typically, mcu ram variables are static ally allocated at assembly time. for example: ; statically allocated ram variables org ramspace myvar1 rmb 1 myvar2 rmb 1 myvar3 rmb 2 ; another method to statically allocate variable myvar4 equ ramspace+4 myvar5 equ ramspace+5 this is appropriate for global vari ables, which need to be available throughout the program flow. however, for local variables only used in specific subroutines, th is method is not most efficient. these variables? ram space can be dynamically allocated by using a software stack or mc u stack, freeing up ram memory. the same method can apply to subroutine input and output parameters, passing them on the stack instead of in the a or x register. the following code shows a software implementation of a stack appropriate for rs08 family of mcus. software stack: ;************************************************************************** ;* a simple software stack implementation simply shows the push and * ;* pull operations on a stack; not intended to be a complete application. * ;* stackptr points to next (empty) available location * ;************************************************************************** ;stack equates stacktop: equ $00000048 stackbottom: equ $0000004f ; ; variable/data section ; org ramstart stackpointer dc.b 1 ;pointer to next stack byte temp dc.b 1 ;temporary storage location free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 stacks freescale semiconductor 6 ; code section org romstart _startup: mainloop: init lda #stackbottom ;initialize stack pointer sta stackpointer feed_watchdog lda #$01 jsr pusha ;write to stack bcs fullerr jsr pusha ;write to stack bcs fullerr jsr pusha ;write to stack bcs fullerr jsr pusha ;write to stack bcs fullerr jsr pusha ;write to stack bcs fullerr jsr pusha ;write to stack bcs fullerr jsr pusha ;write to stack bcs fullerr jsr pusha ;write to stack bcs fullerr jsr pusha ;write to full stack bcs fullerr read jsr pulla ;read from stack bcs emptyerr jsr pulla ;read from stack bcs emptyerr jsr pulla ;read from stack bcs emptyerr loop bra init ;your code here emptyerr dec stackpointer ;your code here bra loop fullerr inc stackpointer ;your code here bra read ;*********************************************************************** ;* push subroutine * ;* push the contents of the accumulator onto stack * ;* use c bit of ccr to indicate full error * ;*********************************************************************** pusha sta temp ;place a in temporary storage lda stackpointer ;get stack pointer cmp #stacktop ;check for full stack blo full ldx stackpointer lda temp ;get a from temporary storage sta $0e ;and save in stack dec stackpointer ;decrement stack pointer clc free datasheet http:///
queues data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 7 rts full lda temp ;get a from temporary storage sec ;set carry bit for error rts ;*********************************************************************** ;* pull subroutine * ;* pull the contents off the stack into accumulator * ;* use c bit of ccr to indicate empty error * ;*********************************************************************** pulla lda stackpointer ;get stack pointer cmp #stackbottom ;check for empty stack beq empty ldx stackpointer incx ;increment stack pointer lda ,x ;get data off stack stx stackpointer ;record new stack pointer clc ;clear carry bit rts empty sec ;set carry bit for error rts using the software stack, a subrou tine can allocate variab les by pushing (allocating) bytes on the stack, accessing them with x (tiny addres s $0f) and d[x] (tiny address $0e), and pulling them (deallocating) before returning. in this way, multiple subroutines can use the same ram space. parameters can also be passed to and from subrout ines. an input parameter can be pushed on the stack. when a subroutine is entered, it can access the input parameter relative to the st ack pointer. by the same token, a subroutine can push an output parameter onto th e stack to be passed back to the calling routine. using the stack to pass parameters and allocate variables optimizes memory usage. 4 queues a queue is a series of elements that accepts data from one end and extracts data from the other end. an analogy for this data structure is a checkout line at th e supermarket; the first pe ople in are the first people out. for this reason, it is cons idered a first-in, first-out (fifo) structure. this is useful when accessing data in the order it is received. a queue usually has a predefined maximum size. figure 3 illustrates a queue. free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 queues freescale semiconductor 8 figure 3. queue 4.1 reading and writing the read operation of a queue is called dequeue, and the write opera tion is enqueue. two pointers are necessary for a queue; one for the head of the line , and one for the tail. for an enqueue operation, after checking the size of the queue, the data is stored at the location the put pointer points to, and the put pointer adjusts. for a dequeue operation, th e data is read from the get-point er location, and the pointer adjusts. queues usually have a fixed size, so track of the num ber of items in the queue. this can be done with a variable containing the size of the queue or with po inter arithmetic. 4.2 queue errors as with the stack structure, a queue can be subject to underflow and overflow errors. the enqueue operation should be non-destructive a nd should error if the queue is fu ll. the dequeue operation should be destructive (remove the data element) and should error if the queue is empty. 4.3 queue applications a practical application of a fifo queue is for a data buffer. queues can be used as buffers for transmitted or received data and for use with pr inters or serial communication devices. an effective application for this is storing data received from the se rial input/output port for processing later. queue software example: ;*********************************************************************** ;*illustrates an example of a queue for rs08 * ;*********************************************************************** ;*********************************************************************** ;*variable/data section * ;*********************************************************************** org ramstart ;insert your data definition here data 1 data 2 data 3 data 4 data 5 empty empty empty dequeue from get pointer enqueue at put pointer data address $50 $51 $52 $53 $54 $55 $56 $57 queue top queue bottom queue grows in this direction free datasheet http:///
queues data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 9 tempa dc.b 1 ;temporary accumulator tempx dc.b 1 ;temporary x register getpointer dc.b 1 putpointer dc.b 1 qcount dc.b 1 qmax dc.b 1 queuetop: equ $44 queuebottom: equ $47 ;*********************************************************************** ;*program code * ;*********************************************************************** org romstart _startup: mainloop: lda #queuebottom ;calculate maximum queue size sub #queuetop inca sta qmax initq lda #queuetop ;initialize q pointer and ; variables sta getpointer sta putpointer clr qcount ;*********************************************************************** ;* write and read from the queue * ;* a good application of this is to place bytes received from * ;* the sci into the queue and retrieve them later * ;* this code does not deal with the error conditions * ;*********************************************************************** jsr dequeue ;will return empty error feed_watchdog lda #$ff jsr enqueue ;will load ff in to $44 jsr enqueue ;will load ff in to $45 jsr enqueue ;will load ff in to $46 jsr enqueue ;will load ff in to $47 and ;wraps back to $44 jsr enqueue ;will return a full error as ;qcount is 4 jsr dequeue ;will pull ff from $44 jsr dequeue ;will pull ff from $45 feed_watchdog lda #$55 jsr enqueue ;will load 55 in to $44 jsr enqueue ;will load 55 in to $45 bra mainloop free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 queues freescale semiconductor 10 ;*********************************************************************** ;* subroutines * ;*********************************************************************** ;*********************************************************************** ;* enqueue - enqueues a data byte passed in accumulator * ;* checks for a full queue and returns a set carry bit if * ;* full otherwise returns a cleared carry bit if successful * ;*********************************************************************** enqueue stx tempx ;save x register contents sta tempa ;save accumulator contents lda qcount ;check for a full q cmp qmax beq qfull lda tempa ;if queue has space restore a ldx putpointer sta $0e ;place a in the queue lda putpointer cmp #queuebottom beq wrapput inc putpointer ;increment pointer if not ;wrapping bra enqdone wrapput lda #queuetop ;if ok move pointer back to ;top of queue sta putpointer enqdone ldx tempx ;restore x register lda tempa ;restore accumulator contents inc qcount ;increment q counter clc ;clear carry bit rts qfull ldx tempx ;restore x register lda tempa ;restore accumulator contents sec ;set carry bit rts ;*********************************************************************** ;* dequeue - dequeues a data byte from queue and return in a * ;* if queue is empty returns a carry set to indicate error * ;* otherwise returns a cleared carry bit and data in a * ;*********************************************************************** dequeue stx tempx ;save x register contents lda qcount ;check for an empty q cmp #$00 beq qempty free datasheet http:///
multiple access ci rcular queue (macq) data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 11 ldx getpointer ;if queue has population lda $0e ;get item from queue sta tempa lda getpointer cmp #queuebottom beq wrapget inc getpointer ;increment pointer bra deqdone wrapget lda #queuetop ;if ok move pointer back to ;top of queue sta getpointer deqdone ldx tempx ;restore x register lda tempa dec qcount ;decrement q counter clc ;clear carry bit rts qempty ldx tempx ;restore x register sec ;set carry bit rts 5 multiple access circular queue (macq) a multiple access circular queue (or ci rcular buffer) is a modified version of the queue data structure. it is a fixed-length, order-preserving data structure and contains the most re cent entries. it is useful for data-flow problems, when only the latest data is of interest. once initialized, it is full , and a write operation discards the oldest data. figure 4 depicts a macq. figure 4. result of a macq write latest data here data address $50 $51 $52 $53 $54 $55 $56 $57 new data data 8 data 7 data 6 data 5 data 4 data 3 data 2 data 8 data 7 data 6 data 5 data 4 data 3 data 2 data 1 free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 multiple access circular queue (macq) freescale semiconductor 12 5.1 applications a macq is useful for data streams requiring the latest data and can afford to have a destructive write operation. for example, a weather for ecaster might use temperature readi ngs from the last five days to predict the next day?s temperature. daily temperature readings can be re corded in a macq, so the latest data is available. macqs are also useful for digital filters; they can calculate running averages, etc. 5.2 example macq illustrates the implem entation of a circular buffer. this coul d store a/d converter readings. in this way, the latest a/d conversion results are accessible through th e circular buffer. macq: ;*********************************************************************** ;*illustrates an example of a macq for rs08 * ;*********************************************************************** ;*********************************************************************** ;*variable/data section * ;*********************************************************************** org ramstart ;insert your data definition here tempa dc.b 1 ;temporary accumulator tempx dc.b 1 ;temporary x register tempdata dc.b 1 ;temporary data storage qpointer dc.b 1 qsize dc.b 1 queuetop: equ $40 queuebottom: equ $47 ;*********************************************************************** ;*program code * ;*********************************************************************** org romstart _startup: mainloop: lda #queuebottom ;calculate maximum queue size sub #queuetop inca sta qsize initq lda #queuebottom ;initialize q pointer sta qpointer ;*********************************************************************** ;* write and read from the macq * ;* a good application of this is to store acmp readings, so * ;* the latest readings are always available * ;*********************************************************************** lda #$55 free datasheet http:///
multiple access ci rcular queue (macq) data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 13 jsr writeq ;writes 55 to $47 lda #$56 jsr writeq ;writes 56 to $46 lda #$57 jsr writeq ;writes 57 to $45 lda #$58 jsr writeq ;writes 58 to $44 lda #$59 jsr writeq ;writes 59 to $43 lda #$5a jsr writeq ;writes 5a to $42 lda #$5b jsr writeq ;writes 5b to $41 lda #$5c jsr writeq ;writes 5c to $40 feed_watchdog jsr writeq ;queue is full on this write ;shifts all entries down one ;writes 5c to $40 lda #$00 jsr readq ;read newest item lda #$01 jsr readq ;reads 2nd newest item lda #$02 jsr readq ;reads 3rd newest item feed_watchdog bra mainloop ;*********************************************************************** ;* subroutines * ;*********************************************************************** ;*********************************************************************** ;* writeq - a contains data to be written. write is * ;* destructive on a full q, once initialized q is always full * ;*********************************************************************** writeq stx tempx ;save x register contents sta tempa ;save a contents lda qpointer ;load q pointer cmp #queuetop-1 ;see if queue is full beq qfull ldx qpointer lda tempa sta $0e ;store data to the queue dec qpointer ;decrement pointer bra qdone ;once queue is initialized, it is always full qfull lda tempa sta tempdata ldx #queuebottom-1 ;start shifting data down swaploop lda $0e ;get 1st item to shift - 2nd free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 tables freescale semiconductor 14 ;last one inc x sta $0e ;store in next queue space ;overwritting last item dec x dec x txa cmp #queuetop ;check to see whether any ;more item to shift bhs swaploop ldx #queuetop lda tempdata sta $0e ;place new item at top of ;queue qdone ldx tempx lda tempa rts ;*********************************************************************** ;* readq - a contains queue index location to be read. * ;* returns value in a * ;*********************************************************************** readq stx tempx ;save x register contents sta tempa ;save a contents add #queuetop ;add queuetop to a tax ;x is adress of desired value lda $0e rts 6tables a table can be viewed as a vector of identically structured lists. a table is a common way of storing lookup data such as display data or vector bytes. figure 5 shows an example of a table. figure 5. table representation $0100 $0500 $0800 $0090 $1200 $2200 $0100 $0100 $50 $51 $52 $53 $54 $55 $56 $57 data address top-of-table pointer free datasheet http:///
tables data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 15 a table is commonly used to look up information. tabl e entries can be accessed wi th an offset from the base address of the table. therefor e, a read from a table is typically done by computing the offset of the desired data and accessing it usi ng an indexed addressing mode. 6.1 table applications the table data structure is common in mcu applications. on e way to use tables is by performing character conversions. for lcds (liquid crysta l displays), an ascii character by te may need to be converted to segment bitmaps for the display. a table could be used for this. another table application is a jump table. this is a ta ble of vector values that are addresses to be loaded and vectored to. some progr am parameters can be converted to an offset into a jump table, so the appropriate vector is fetched for a certain input. for example, in their memory maps, freescale mcus have a built-in vector table used for interrupt and exception processing. these vector ta bles allow pre-programmed addresse s to be defined for certain mcu exceptions. when an exception occurs, a new program-co unter value is fetched from the appropriate table entry. you can also use the table data st ructure by storing predefined values for lookup. (for example, storing interpolation data in a table performing mathematical functions). this use of a table is documented in the application note, ?integer math routines fo r rs08,? freescale document order number, an3348. another example involves using a table of sinusoidal values to pr oduce sine-wave output, as in the application note ?arithmeti c waveform synthesis with the hc05/ 08 mcus,? freescale document order number an1222. if an equation to calcula te data is cpu-intensive and ca n be approximated with discrete values, these values can be precalculated and stored in a table. in this way, a value can be quickly fetched, saving cpu time. 6.2 table example an example of the use of tables to co nvert ascii data to lcd segment values: ;*********************************************************************** ;*variable/data section * ;*********************************************************************** org ramstart ;insert your data definition here lcd1 dc.b 1 lcd2 dc.b 1 ;*********************************************************************** ;*program code * ;*********************************************************************** org romstart _startup: mainloop: lda #73 ;load an ascii character - i jsr convert ;convert the character into a ;table offset mov #$e1,pagesel ;change memory page to access ;table free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 tables freescale semiconductor 16 add #$c0 ;alternative code for "change memory page to access table" ;mov #high_6_13(table),pagesel ;sta map_addr_6(table) tax ;transfer offset in to x lda $0e ;load the first byte sta lcd1 ;store in data register incx lda $0e ;load the second byte sta lcd2 ;store in data register bra mainloop ;*********************************************************************** ;* convert ascii character byte in a to an offset value into * ;* the table of lcd segment values. valid ascii values are * ;* (decimal): 65-90 * ;*********************************************************************** convert cmp #65 ;check for numeric blo converror cmp #91 ;check for invalid values bhs converror sub #65 ;convert to table offset bra convdone converror clra ;invalid value shows as blank convdone rola ;multiply offset by 2 as ;2 bytes per lcd location rts ;*********************************************************************** ;* lcd lookup table * ;* lookup table of lcd segment values for ascii character * ;* values. some characters can not be displayed on 15-segment * ;* lcd, so they are marked as invalid, and will be displayed * ;* as a blank space. * ;* ensure table fits within one page * ;*********************************************************************** org $3840 table fdb $2764 ;'a' fdb $8785 ;'b' fdb $01e0 ;'c' fdb $8781 ;'d' fdb $21e4 ;'e' fdb $2164 ;'f' fdb $05e4 ;'g' fdb $2664 ;'h' fdb $8181 ;'i' fdb $06c0 ;'j' free datasheet http:///
linked lists data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 17 fdb $206a ;'k' fdb $00e0 ;'l' fdb $1662 ;'m' fdb $1668 ;'n' fdb $07e0 ;'o' fdb $2364 ;'p' fdb $07e8 ;'q' fdb $236c ;'r' fdb $25a4 ;'s' fdb $8101 ;'t' fdb $06e0 ;'u' fdb $4062 ;'v' fdb $4668 ;'w' fdb $500a ;'x' fdb $9002 ;'y' fdb $4182 ;'z' endtable equ *-table ;end of table label 7 linked lists a list is a data structure whose elements may vary in precision. for example, a re cord containing a person?s name, address, and phone number coul d be considered a list. a linked list is a group of lists, each containing a pointer to another list. figure 6 represents a linked list. figure 6. linked list each list in the structure contains th e same type of informat ion, including a link to th e next item in the list. the link might be an absolute address or an offset fr om a base address. in a doubly linked list, pointers are kept to the next and previous item in the list. a linked list can be trav ersed easily by simply following the pointers from one list to the next. nextptra ne xtptrc nextptrb data1a data2a data3a data4a data1b data2b data3b data4b data1c data2c data3c data4c lis ta l istb lis tc free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 linked lists freescale semiconductor 18 7.1 linked list applications traditionally, a linked list defines a dynamically allocated database, in which the elements can be ordered or resorted by adjusting the links. however, in a smal l mcu, there are more appr opriate applications of linked lists. a linked list can be a structure for a command inte rpreter. each command coul d contain the string of characters, an address of a subroutin e to call on that comma nd, and a link to the next command in the linked list. in this way, a command string could be input, sear ched for in a linked list, and appropriate action taken when the string is found. 7.2 state machines another useful applicat ion of a linked list is defi ning a state machine. a stat e machine can be represented by a discrete number of states, each having an output and pointers to th e next state(s). see figure 7 . figure 7. state machine a state machine can be considered a mealy or a moore machine. a me aly machine?s output is a function of both its inputs and its current state. a moore m achine has an output depende nt only on its current state. this state machine model can be useful for contro lling sequential devices su ch as vending machines, stepper motors, or robotics. these machines have a current internal state, receive input, produce output, and advance to the next state. you can first model a process as a se quential machine, then convert this behavior to a linked-list structure and write an interpreter for it. modify the state mach ine by changing the data structure (linked list) and not the code. state c state d state a state b 0/1 1/1 0/1 0/0 1/0 0/0 1/1 1/0 input/output free datasheet http:///
linked lists data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 19 7.3 state machine example imagine you want to cross the street . before you can safely cross, you must push th e pedestrian-crossing controller. the controller has two li ght patterns: one for automobile light s and one for the pedestrian lights. to activate the pedestrian-crossing, you must pr ess a button at the side of the road. see figure 8 . figure 8. pedestrian crossing controller example this is like a moore state machine: it s output is a function of its current state. the next state is a function of the current state and the state of the input. figure 9 shows a state graph for this example. the initial state is a green light on the automobile li ghts and a red light for the pedestrian s. the controller remains in this state until a pedestrian?s i nput. the flow continues as shown in the diagram. the output is a pattern for the light array to activate the lights for the state. figure 9. pedestrian crossing controller state machine pedestrian lights automobile lights state 1 output = 00001010 delay = 30 input = 0 input = 1 state 2 output = 00010010 delay = 5 input = 1 or 0 input = 1 or 0 input = 1 or 0 state 3 output = 00100001 delay = 15 state 4 output = 0010000t delay = 10 free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 linked lists freescale semiconductor 20 7.4 simulation this example can be simulated using leds a nd a mc9rs08ka2 mcu. a push-button switch can simulate the input sensor. figure 10 illustrates the simulation circuit. us ing five bits of an output port, a pattern can be generate d to display the appr opriate lights (leds). table 1 shows the bitmap in this application. figure 10. circuit simulation of pedestrian crossing controller table 1. pedestrian crossing lights bitmap for port a with the hardware in place, the last step is defining the state machine in softwa re. do this by implementing a linked-list data structure and the c ode to access and interpret the machine. for this example, each list in the data structure define s the current state of the lights. each list contains: ? the byte that is the bitmap for the lights. ? a delay value ? the time the controller remains in the state ? the next state pointer for an input of 0 car ped state rygbuttonrg pta5 pta4 pta3 pta2 pta1 pta0 100 10 10 20 101 10 3 100x0 1 4 100x0 flashing pta0 pta3 pta4 pta1 pta5 mc9rs08ka2 pta2 g r g r y outputs outputs inputs vdd 1k 1k 1k 0.1f free datasheet http:///
linked lists data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 21 ? the next state pointer for an input of 1 the program?s main loop should execu te the program flow charted in figure 11 . figure 11. state machine program flow pedestrian-crossing controller state machine: ;*********************************************************************** ;* pedestrian crossing signal/lights controller example. * ;* illustrates a linked list implementation of a state machine for * ;* the mc9rs08ka2 * ;*********************************************************************** ;*********************************************************************** ; macro to manage nested subroutine entry code * ;*********************************************************************** entry_code: macro sha sta pcbuffer+(2*(\1)) sha sla sta pcbuffer+(2*(\1))+1 sla endm ;*********************************************************************** ; macro to manage nested subroutine exit code * ;*********************************************************************** exit_code: macro sha lda pcbuffer+2*(\1) sha get input input = 0 input = 1 load next state pointer (offset) (offset) state pointer load next pattern light output load initial state delay for given value free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 linked lists freescale semiconductor 22 sla lda pcbuffer+2*(\1)+1 sla endm ; include derivative-specific definitions include 'derivative.inc' ;*********************************************************************** ;*variable/data section * ;*********************************************************************** xdef _startup absentry _startup maxlevel equ 1 ;nesting depth for subroutine ;macro org ramstart ;insert your data definition here tempa dc.b 1 tempx dc.b 1 delaycntr dc.b 1 pcbuffer ds.w maxlevel ;buffer for return address of ;nested subroutine macro ;*********************************************************************** ;*program code * ;*********************************************************************** org romstart _startup: mainloop: mov #$c0,icsc2 ;select bus frequency of 1mhz lda #$00 sta ptad ;predefine output levels lda #$33 sta ptadd ;gpio pta 0, 1, 3, 4, 5 outputs mov #$e4,pagesel ;change memory page to access ;table lda #states ;index initial space add #$c0 ;alternative code for "change memory page to access table" ;mov #high_6_13(state1),pagesel ;lda map_addr_6(state1) tax loop lda $0e ;get light pattern sta ptad ;output light pattern cmp %00100000 ;check to see if in state 4 bne loaddelay free datasheet http:///
linked lists data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 23 jsr togglewalk loaddelay incx lda $0e ;get delay bra secdelay ;cause delay nextstate mov #$e4,pagesel ;change memory page to access ;table ;alternative code for "change memory page to access table" ;mov #high_6_13(state1),pagesel brclr 2,ptad,input0 ;check for pedestian input input1 incx incx lda $0e add #$c0 sta $0f ;get next state offset bra loop ;input = 1 input0 mov #$e4,pagesel ;change memory page to access ;table incx lda $0e add #$c0 sta $0f ;get next state offset bra loop ;input = 0 togglewalk incx lda $0e ;get delay flashlight bset 0,ptad jsr delay0 ;turn led on for ~0.5 second bclr 0,ptad jsr delay0 ;turn led off for ~0.5 second deca cmp #00 beq input0 ;branch to "input 0" routine ;if 10 seconds have passed bra flashlight ;else repeat flash ;*********************************************************************** ;* delay subroutines * ;*********************************************************************** ;* cause a delay of approx (1 second * accumulator value) @ fop = 1m * ;* delay value passed in through a * ;*********************************************************************** secdelay: feed_watchdog cmp #$00 beq secdone jsr delay0 jsr delay0 ;1 sec delay (2 x 0.5 sec) free datasheet http:///
data structures for rs08 microcontrollers, rev. 0 linked lists freescale semiconductor 24 deca bra secdelay secdone bra nextstate ;*********************************************************************** ;* cause a delay of ~1/2 of a second * ;*********************************************************************** delay0: entry_code 0 feed_watchdog sta tempa lda #$b2 dloop0 cmp #$00 beq ddone0 jsr delay1 deca bra dloop0 ddone0 lda tempa exit_code 0 rts ;*********************************************************************** ;* cause about 2.8msec delay @ fop of 1mhz * ;*********************************************************************** delay1: entry_code 1 feed_watchdog sta delaycntr lda #$ff dloop1 cmp #$00 beq ddone1 deca bra dloop1 ddone1 lda delaycntr exit_code 1 rts ;*********************************************************************** ;* datastructure for state machine linked list * ;* offsets and base address scheme is adequate for small * ;* table (<255 bytes) * ;*********************************************************************** org $3900 lights equ 0 ;offset for light pattern delay equ 1 ;offset for time delay next0 equ 2 ;offset for pointer 0 next1 equ 3 ;offset for pointer 1 states equ * ;base address of states ;* cars green, pedestrians red state1 equ *-states ;offset into states free datasheet http:///
summary data structures for rs08 microcontrollers, rev. 0 freescale semiconductor 25 fcb %00001010 ;output for state fcb 30 ;delay for state fcb state1 ;next state for input of 0 fcb state2 ;next state for input of 1 ;* cars yellow, pedestrians red state2 equ *-states fcb %00010010 fcb 5 fcb state3 fcb state3 ;* cars red, pedestrians green state3 equ *-states fcb %00100001 fcb 15 fcb state4 fcb state4 ;* cars red, pedestrians flashing green state4 equ *-states fcb %00100000 ;green initially off when state ;entered fcb 10 fcb state1 fcb state1 8summary the use of data structures is not limited to large, co mplicated computers. althoug h the data structure is a powerful concept in such a context, the same princi ples apply to smaller pr ocessors such as 8-bit microcontrollers. the code to implement these data structures does not have to be complex or confusing. the goal of programming should be to modulari ze commonly used functions, so th ey may be reused in other applications with minimal modification. data structure concepts can improve the static and dynamic performanc e of an mcu application without affecting its portabil ity or legibility. free datasheet http:///
document number: AN3334 rev. 0 11/2006 how to reach us: home page: www.freescale.com e-mail: support@freescale.com usa/europe or locations not listed: freescale semiconductor technical information center, ch370 1300 n. alma school road chandler, arizona 85224 +1-800-521-6274 or +1-480-768-2130 support@freescale.com europe, middle east, and africa: freescale halbleiter deutschland gmbh technical information center schatzbogen 7 81829 muenchen, germany +44 1296 380 456 (english) +46 8 52200080 (english) +49 89 92103 559 (german) +33 1 69 35 48 48 (french) support@freescale.com japan: freescale semiconductor japan ltd. headquarters arco tower 15f 1-8-1, shimo-meguro, meguro-ku, tokyo 153-0064 japan 0120 191014 or +81 3 5437 9125 support.japan@freescale.com asia/pacific: freescale semiconductor hong kong ltd. technical information center 2 dai king street tai po industrial estate tai po, n.t., hong kong +800 2666 8080 support.asia@freescale.com for literature requests only: freescale semiconductor literature distribution center p.o. box 5405 denver, colorado 80217 1-800-441-2447 or 303-675-2140 fax: 303-675-2150 ldcforfreescalesemiconduc tor@hibbertgroup.com information in this document is provid ed solely to enable system and software implementers to use freescale semiconduc tor products. there are no express or implied copyright licenses granted hereunder to design or fabricate any integrated circuits or integrated circuits based on the information in this document. freescale semiconductor reserves the right to make changes without further notice to any products herein. freescale semiconductor makes no warranty, representation or guarantee regarding the suitability of its products for any particular purpose, nor does freescale semiconductor assume any liability arising out of the application or use of any product or circuit, and specif ically disclaims any and all liability, including without limitation consequential or incidental damages. ?typical? parameters that may be provided in freescale semiconductor data s heets and/or specifications can and do vary in different applications and actual performance may vary over time. all operating parameters, including ?typicals?, must be validated for each customer application by customer?s technical experts. freescale semiconductor does not convey any license under its patent rights nor the rights of others. freescale semiconductor products are not designed, intended, or authorized for use as components in systems intended for surgical implant into the body, or other applic ations intended to support or sustain life, or for any other application in which the failure of the freescale semiconductor product could create a situation where personal injury or death may occur. should buyer purchase or use freescale semiconductor products for any such unintended or unauthorized application, buyer shall indemnify and hold freescale semiconductor and its officers, employees, subsidiaries, affiliates, and distributors harmless against all claims, costs, damages, and expenses, and reasonable attorney fees arising out of, directly or indirectly, any claim of personal injury or death associated with such unintended or unauthorized use, even if such claim alleges that freescale semiconductor was negligent regarding the design or manufacture of the part. freescale? and the freescale logo are trademarks of freescale semiconductor, inc. all other product or service names are the property of their respective owners. ? freescale semiconductor, inc. 2006. all rights reserved. rohs-compliant and/or pb-free versions of freescale products have the functionality and electrical characteristics as thei r non-rohs-compliant and/or non-pb-free counterparts. for further information, see http://www.freescale.com or contact your freescale sales representative. for information on freescale?s environmental products program, go to http://www.freescale.com/epp . free datasheet http:///

▲Up To Search▲

Price & Availability of AN3334

	To Download AN3334 Datasheet File
If you can't view the Datasheet, Please click here to try to view without PDF Reader .